package JZOffer;

/**
 * 剑指 Offer 60. n个骰子的点数
 * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。
 * 输入n，打印出s的所有可能的值出现的概率。
 *
 * 你需要用一个浮点数数组返回答案，
 * 其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
 * 示例 1:
 * 输入: 1
 * 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
 *
 * 示例 2:
 * 输入: 2
 * 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
 * */

class Solution60 {
    public double[] dicesProbability (int n) {
        double[] dp = new double[6 * n -(n - 1)];
        for (int i = 0; i < 6; i++) {
            dp[i] = 1.0/6.0;
        }
        for (int i = 2; i <= n; i++) {
            //第i个骰子对应的最大位置
            int mi = 6 * i - (i - 1);
            //按逆序查找
            for (int j = mi - 1; j >= 0; j--){
                //找到上一轮第i-1个骰子,
                //如 3个骰子的话，那么点数18应该是2个骰子投出12-17的概率和
                //3个骰子点数17应该是2个骰子投出11-16的点数的概率和。。类推

                //应该是相对第i-1个骰子平移了一个位置,i-1的12对应i的13
                double p = 0;
                for (int k = j; k >= 0 && k >= j - 5; k--) {
                    p += dp[k]/6.0;
                }
                dp[j] = p;
            }
        }
        return dp;
    }
}